The following invention relates generally to the improved operation of a usage parameter control (UPC) device for asynchronous transfer mode (ATM) communications systems, and in particular, to following wrapping of finite counter and register elements used to keep track of infinitely progressing time.
In recent years, ATM communication has become increasingly popular. Prior to this preference for ATM, time division multiplexing (TDM) systems were the preferred mode of communication. In TDM systems, each user was allocated a particular time slot within a standard time interval during which a communication channel would be dedicated to the user. In this system, the time slot would be unavailable to other users regardless of whether the allocated user was actually using it which frequently resulted in wasted bandwidth.
In ATM systems, by contrast, information is transmitted as bandwidth is available without regard to time. In order to keep ATM traffic flowing, each user agrees, by way of a contract with the ATM network operator, to a minimum length of time, t, between transmission of his or her cells. A maximum number of cells which may be transmitted in an interval, T, is also agreed upon. The time, t, determines the user""s peak cell rate (PCR) and the interval, T, determines the user""s sustained cell rate (SCR). A third parameter, maximum burst size (MBS) which specifies the maximum number of cells which are permitted to be transmitted consecutively at the PCR, is also contracted for. In order to prevent users from exceeding their respective limitations, ATM networks may employ a UPC device which can monitor these and other usage parameters.
In an ATM system, UPC monitoring is typically performed in accordance with standard generic cell rate algorithms (GCRAs). Once such GCRA is a xe2x80x9cleaky bucketxe2x80x9d algorithm, in which a figurative bucket xe2x80x9cfillsxe2x80x9d proportional to the actual cell rate received from a user and xe2x80x9cdrainsxe2x80x9d at a fixed rate proportional to the contracted service rate parameters. If the user exceeds the limits on contracted parameters, such as PCR or SCR, the xe2x80x9cbucketxe2x80x9d will xe2x80x9coverflowxe2x80x9d and the user""s cells may be either discarded or tagged as having a low priority.
ATM communications may be carried out using a constant bit rate (CBR) or using a variable bit rate (VBR). A CBR connection essentially mimics the old TDM systems. Monitoring of a CBR connection is accomplished using a single leaky bucket. Conformance is characterized by the peak cell rate (PCR) and the corresponding cell delay variation tolerance (CDVT) due to, e.g., head-of-line blocking. The CDVT is defined in relation to the PCR. The capacity of the leaky bucket is 1/PCR (a.k.a. IP)+CDVT specified for the cell flow. The drain rate of the PCR bucket is 1/PCR.
FIG. 1 is a flow chart illustrating the operation of a leaky bucket GCRA used to monitor usage parameters for a CBR connection. In block 102, a cell arrives at time TTA. Thereafter TTATp for the particular user is read from memory in block 105. TTATp is the time value at which the xe2x80x9cbucketxe2x80x9d will have drained to an empty condition in the absence of new cell arrivals. It is calculated during cell arrivals and is adjusted in proportion to the contracted PCR rate for CBR service. In Block 107 a comparison between TTA and TTATp is performed. If TTA is greater than TTATp, i.e. the cell arrived after the bucket had completely emptied, then the cell is accepted at block 111, and, at block 114, TTATp is set to TTA+1/PCR. If TTA is not greater than TTATp, i.e. the bucket is not completely empty, a check is done in block 117 to determine if there is enough room in the partially full bucket to accept the cell based on its maximum capacity of 1/PCR+ CDVT. If not, the cell is discarded at block 120. If so, the cell is accepted at block 122, and TTATp is updated at block 125 to equal TTATp+1/PCR.
In a variable bit rate (VBR) system, a second leaky bucket GCRA is used in addition to the first leaky bucket GCRA described above in order to ensure compliance with the contracted sustained cell rate (SCR) and maximum burst size (MBS). The capacity of this second leaky bucket is 1/SCR+Burst Tolerance (BT)+CDVT. Burst tolerance is calculated from the contracted SCR, PCR, and MBS, and is the additional bucket depth required to hold xe2x80x9cMBS-1xe2x80x9d more cells arriving at the PCR rate (BT={MBSxe2x88x921}xc3x97{1/SCRxe2x88x921/PCR}). The sum of BT and CDVT is given the identifier xe2x80x9cLxe2x80x9d. The drain rate of this bucket is 1/SCR.
FIG. 2 shows the flow diagram for this second GCRA for the case where it is used in conjunction with the GCRA of FIG. 1. If a cell is accepted in accordance with the GCRA of FIG. 1, i.e., either of boxes 128 or 131 of FIG. 1 are reached, then TTATs is retrieved from memory in block 137. TTATs is the time value at which the xe2x80x9cbucketxe2x80x9d will have drained to an empty condition in the absence of new cell arrivals, and is calculated in increments of 1/SCR which provides enough time for a full bucket to leak enough to provide room for another cell. A comparison between the TTA of the cell from box 102 of FIG. 1 and the theoretical arrival time, TTATs, is then performed at box 140.
If the result of the comparison of box 140 is that TTA is greater than TTATs, then the cell is accepted at box 143, and TTATs is set to TTA+1/SCR at box 146. If the result of box 140 is that TTA is not greater than TTATs, then the system checks at box 149 to see whether the sum of TTA plus the burst tolerance (BT) plus the CDVT is greater than TTATs, where BT is a function of the contracted parameters MBS, PCR and SCR. If not, the cell is non-conforming and is discarded at box 152. If, on the other hand, the condition TTA+BT+CDVT greater than TTATs is met, the cell is accepted at box 155 and TTATs is set to TTATs+1/SCR at box 158.
A brief example using simple, if not practical, hypothetical figures for SCR, MBS and PCR will better illustrate the operation of the leaky bucket of FIG. 2. Assuming a VBR service with contracted parameters of SCR=5 cells/sec, a MBS=3 cells, and a PCR of 100 cells/sec and CDVT of 0.02 sec. This results in 1/SCR=IS=0.2 sec/cell, BT=0.38 sec, and L=BT+CDVT=0.4 sec. For the purposes of this example, assume that the criteria of the first leaky bucket check against PCR and CDVT is always favorable and that the initial value of TTATs is 0.0. If a first cell is transmitted at 0.01 seconds, i.e., TTA=0.01, the result of box 140 is that TTA greater than TTATs so that the cell is accepted at box 143 and TTATs is set to TTATs+1/SCR, i.e., 0.0+0.2=0.2 sec at box 146. A second cell now arrives at time 0.02 seconds. The result of box 140 is that TTA less than TTATs so that the condition TTA+L greater than TTATs is checked at box 149. We find that this condition is met (0.02+0.4 greater than 0.2). The cell is accepted at box 155 and TTATs is set to TTATs+1/SCR, i.e., 0.2+0.2=0.4 sec at box 158. Similarly, a third cell arrivals at 0.03 sec, the cell is accepted and TTATs is set to 0.6 sec. If a fourth cell arrives at 0.04 sec, TTA+L will not be greater than TTATs. The fourth cell is therefore discarded at box 152 and TTATs remains unchanged at 0.6 sec. The same result occurs for any cell received earlier than time 0.2 seconds. After that time, the condition TTA+L greater than TTATs of box 149 is again met. Furthermore, if the fifth cell does not arrive until a time later than 0.6 sec, the bucket will be completely empty and the TTA greater than TTATs condition will be met.
Those skilled in the art will appreciate that the above description is a simplified explanation of ATM systems, the role of UPC devices and leaky buckets generally. With respect to ATM systems, detailed explanations of the operation of such systems may be found in User Network Interface Specification (UNI) 3.1 published by the ATM Forum. The present invention is intended for use in systems designed in accordance with the standards presented therein, but is not so limited. Moreover, leaky bucket GCRAs have myriad design applications in which the present invention may be employed.
While the UNI Specification provides broad standards for designing ATM systems, there is little or no guidance provided for many practical problems encountered in implementation. One such problem is that counters and registers of infinite memory are not available to keep track of time, and finite-memory counters and registers will eventually reach their limit and reset to zero. This problem is hereafter referred to as xe2x80x9cwrapping.xe2x80x9d A wrapping of the current time counter from which the cell arrival time TTA is read and/or the register which stores TTA without a consequent wrapping of the register which stores the theoretical arrival time TTAT will cause subsequent comparisons between TTAT and TTA to yield unwanted results. For example, if the current time counter wraps to zero, it will appear that the arrival time, TTA, is much earlier than it actually is, and the comparison between TTA and TTAT will show that TTA is less than TTAT, indicating a violation of the contracted transmission rate when, in fact, no such violation occurred.
In accordance with the present invention, in a usage parameter control device for an asynchronous transfer mode communications system, a determination is made as to whether either of the respective storage elements maintaining values for (1) the time of arrival of a cell (TTA) and (2) the time value at which the xe2x80x9cbucketxe2x80x9d will have drained to an empty condition (TTAT) has wrapped relative to the other. The determination is made prior to comparing the TTA and TTAT values in order to determine whether the user is complying with his or her contracted parameters.
In accordance with a further aspect of the invention, a wrap state is maintained for each virtual connection (VC). A wrap state indicates the wrap status of the respective storage elements maintaining values for TTA and TTAT relative to one another. The comparisons between TTA and TTAT which determine whether a user is in conformance with his or her contracted parameters are then modified accordingly. The wrap state for each VC is updated during a wrap audit each time the current time counter, i.e., the counter from which TTA is read, wraps.
In accordance with a further aspect of the invention, in order to avoid excessive delays in cell processing which may be caused by the wrap audit in a system capable of maintaining a relatively large number of VCs, the VCs are divided into a predetermined number of groups and the current time counter is divided into an equal number of phases such that wrap state audits are performed on a staggered group-by-group basis.
It is therefore an object of the present invention to provide a UPC system which will take into account the wrapping of storage elements containing the values of TTAT and TTA.
It is a further object of the present invention to provide a UPC system with the ability to perform wrap audits for each VC on a regular basis without causing unacceptable delay to the function of the ATM system.
For a better understanding of the present invention, together with other and further objects, reference is made to the following description, taken in conjunction with the accompanying drawings and its scope will be pointed out in the appended claims.